package com.cat.dynamicPlanning02;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/sort-integers-by-the-power-value/?envType=problem-list-v2&envId=dynamic-programming
 * @create 2025/11/6 15:11
 * @since JDK17
 */

public class Solution47 {
    Map<Integer, Integer> map = new HashMap<>();
    int dfs(int x) {
        if (map.containsKey(x)) {
            return map.get(x);
        }
        if (x == 1) {
            return 0;
        }
        if (x % 2 == 0) {
            map.merge(x, 1 + dfs(x / 2), Integer::sum);
        } else {
            map.merge(x, 1 + dfs(x * 3 + 1), Integer::sum);
        }
        return map.get(x);
    }

    public int getKth(int lo, int hi, int k) {
        Integer[] h = new Integer[hi - lo + 1];
        Arrays.setAll(h, i -> i + lo);
        Arrays.sort(h, (a, b) -> dfs(a) - dfs(b));
        return h[k - 1];
    }
}
